<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Maximum Size Rectangle of All 1's Dynamic Programming</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="maximum-size-rectangle-of-all-1s-dynamic-programming">Maximum Size Rectangle of All 1's Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=g8bSdXCG-lA&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=18">https://www.youtube.com/watch?v=g8bSdXCG-lA&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=18</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumRectangularSubmatrixOf1s.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumRectangularSubmatrixOf1s.java</a></li>
</ul>
<p>将2维问题转换为1维问题， 时间复杂度O(col * row), 空间复杂度 O(col)</p>
<h1 id="1-先求一维问题">1. 先求一维问题</h1>
<ul>
<li>
<ol start="84">
<li>Largest Rectangle in Histogram</li>
</ol>
</li>
<li><a href="https://leetcode.com/problems/largest-rectangle-in-histogram/">https://leetcode.com/problems/largest-rectangle-in-histogram/</a></li>
<li><a href="https://www.youtube.com/watch?v=ZmnqCZp9bBs&amp;list=PLrmLmBdmIlptv-uwAgP8k5pGdlHedncq1">https://www.youtube.com/watch?v=ZmnqCZp9bBs&amp;list=PLrmLmBdmIlptv-uwAgP8k5pGdlHedncq1</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -&gt; int:</span>
        heights.append(<span class="hljs-number">0</span>)
        stack = []
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i,height <span class="hljs-keyword">in</span> enumerate(heights):
            <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> heights[stack[<span class="hljs-number">-1</span>]] &gt;= height:
                i2 = stack.pop()
                <span class="hljs-keyword">if</span> stack:
                    ans = max(ans, heights[i2] * (i - stack[<span class="hljs-number">-1</span>] - <span class="hljs-number">1</span>))
                <span class="hljs-keyword">else</span>:
                    ans = max(ans, heights[i2] * i)
            stack.append(i)
        <span class="hljs-keyword">return</span> ans
    
</div></code></pre>
<h1 id="2-借助一维的解法再求二维问题">2. 借助一维的解法，再求二维问题</h1>
<ul>
<li>累加第1行， maxArea = 3</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp11d.png" alt="dp11d.png"></p>
<ul>
<li>累加第2行， maxArea = 3</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp11c.png" alt="dp11c.png"></p>
<ul>
<li>累加第3行， maxArea = 5</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp11b.png" alt="dp11b.png"></p>
<ul>
<li>累加第4行， 最终答案 maxArea = 8</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp11.png" alt="dp11.png"></p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights)</span> -&gt; int:</span>
        heights.append(<span class="hljs-number">0</span>)
        stack = []
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i,height <span class="hljs-keyword">in</span> enumerate(heights):
            <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> heights[stack[<span class="hljs-number">-1</span>]] &gt;= height:
                i2 = stack.pop()
                <span class="hljs-keyword">if</span> stack:
                    ans = max(ans, heights[i2] * (i - stack[<span class="hljs-number">-1</span>] - <span class="hljs-number">1</span>))
                <span class="hljs-keyword">else</span>:
                    ans = max(ans, heights[i2] * i)
            stack.append(i)
        <span class="hljs-keyword">return</span> ans
    
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxRectangeOnes</span><span class="hljs-params">(self, matrix)</span>:</span>
        m = len(matrix)
        n = len(matrix[<span class="hljs-number">0</span>])
        row = [<span class="hljs-number">0</span>] * n
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> matrix[i][j] == <span class="hljs-number">0</span>:
                    row[j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    row[j] += matrix[i][j]

            ans = max(ans, self.largestRectangleArea(row))
        <span class="hljs-keyword">return</span> ans

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>:</span>
    matrix = [
        [<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>],
        [<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>],
        [<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>],
        [<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">1</span>],
    ]
    s = Solution()
    pprint(matrix)
    r = s.maxRectangeOnes(matrix)
    print(<span class="hljs-string">f"r=<span class="hljs-subst">{r}</span>"</span>)

<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">'__main__'</span>:
    main()

</div></code></pre>

    </body>
    </html>